/**
 * Program 3.9 Circular list example (Josephus problem)
 * -------------------------------------------------------------
 * To represent people arranged in a circle, 
 * 
 * we build a circular linked list, with a link from each person to the person on the left in the circle.
 * - The integer i represents the ith person in the circle.
 * 
 * After building a one-node circular list for 1, we insert 2 through N after that node, resulting in a circle with 1 through N, leaving x pointing to N.
 * 
 * Then, we skip $M - 1$ nodes, beginning with 1, and set the link of the $(M - 1$st to skip the $M$th, continuing until only one node is left.
 * 
 */
#include <stdlib.h>
#include <stdio.h>
#include "Item.h"

typedef struct node *link;

struct node {
    Item item;
    link next;
};

int main(int argc, char **argv) {
    if (argc != 3) {
        printf("Usage:%s N M\n", argv[0]);
        return 1;
    }
    int N = atoi(argv[1]);
    int M = atoi(argv[2]);
    int i;

    link t = malloc(sizeof(*t));
    t->item = 1;
    t->next = t;

    link x = t;

    //在节点x之后插入t
    for (i = 2; i <= N; i++) {
        t = malloc(sizeof(*t));
        t->item = i;
        t->next = x->next;
        x->next = t;
        x = t;
    }

    while (x->next != x) {
        for (i = 1; i < M; i++) {
            x = x->next;
        }
        t = x->next;
        x->next = t->next;
        printf("%d ", t->item);
        free(t);
        N--;
    }
    printf("\n");
    printf("%d\n", x->item);


    return 0;
}